﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

partial class Program
{
   static string S = "where are you?who is this?what did I do?"
                   + "what may I eat?who are you?who will I eat?who may I eat?who shall I eat?"
                   + "eye of newt for a charm of powerful trouble."
                   + "like hell broth boil and bubble."
                   + "the devils voice, sweet to hear."
                   + "mom is that you?daddy is that you?"
                   + "deep into the darkness peering."
                   + "dreaming dreams no mortal dare dream."
                   + "the glimmer of the half extinguished light."
                   + "I saw the dull yellow eye of the creature open."
                   + "now the very witching time of night. hell itself breathes "
                   + "out contagion to this world."
                   + "all work and no play make jack crazy."
                   + "heres jack cheese!"
                   + "there are so many people that witness these things. I dont see how one couldnt "
                   + "believe these things. hard to believe that it is all in your head."
                   + "gentle hands help the dead."
                   + "friendly milk broth will countermand my trousers."
                   + "yellow dreams sleep furiously."
                   + "charm for mommy."
                   ;
   static Dictionary<string,string[]> NonStart = new Dictionary<string,string[]>();
   static string[] Starts;
   static Dictionary<string,string> Terminal = new Dictionary<string,string>();

   static string GenerateSentence()
   {
      StringBuilder SB = new StringBuilder();
      string Word = Starts[ Rnd . Next(0, Starts . Length) ];

      Transition(SB, Word);
      return SB . ToString();
   }

   static void Transition(StringBuilder SB, string Word)
   {
      while (true)
      {
         SB . Append(Word);
         SB . Append(' ');

         // Look up word after this
         string[] Nexts;
         if (!NonStart . TryGetValue(Word, out Nexts))
           break;
         int Idx = Rnd . Next(Terminal . ContainsKey(Word) ? -1 :0, Nexts . Length);
         if (Idx < 0)
           break;
         Word = Nexts [Idx];
      }
   }


   // Build a map of words to the next word, and their probability
   static void BuildSuffixTree()
   {
      // First, build up a list of words that start sentence, and transitions
      List<string> Starts1 = new List<string>();
      Dictionary<string,List<string>> Trans = new Dictionary<string,List<string>>();
      foreach(string S1 in S . Split(new char[]{'.','?','!'}))
      {
         string Prev=null;
         foreach(string S2 in S1 . Split(new char[]{' ','\n','\r','\t',',',';'}))
         {
            if (S2 . Length < 1)
              continue;
            if (null == Prev)
              {
                 Starts1 . Add(string . Intern(S2 . ToLower()));
                 Prev = string . Intern(S2 . ToLower());
                 continue;
              }
            List<string> Nextsa;
            if (! Trans . TryGetValue(Prev, out Nextsa))
              Trans[Prev] = Nextsa = new List<string>();
            Prev = string . Intern(S2 . ToLower());
            Nextsa . Add(Prev);
         }
         if (null != Prev)
           Terminal[Prev] = Prev;
     }

     // Next, flatten the list of words that start a sentence
     Starts = Starts1 . ToArray();

     // Flatten the transition table
     foreach (string S3 in Trans . Keys)
      NonStart[S3] = Trans [S3] . ToArray();
   }
}
